import java.io.PrintStream;
import java.util.Arrays;

public class p2 {
    public p2() {
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, -2, 3, 5, -1};
        PrintStream var10000 = System.out;
        String var10001 = Arrays.toString(nums1);
        var10000.println("Max subarray sum for " + var10001 + " is " + max(nums1));
        int[] nums2 = new int[]{1, -2, 3, -8, 5, 1};
        var10000 = System.out;
        var10001 = Arrays.toString(nums2);
        var10000.println("Max subarray sum for " + var10001 + " is " + max(nums2));
        int[] nums3 = new int[]{1, -2, 3, -2, 5, 1};
        var10000 = System.out;
        var10001 = Arrays.toString(nums3);
        var10000.println("Max subarray sum for " + var10001 + " is " + max(nums3));
    }

    public static int max(int[] nums) {
        if (nums != null && nums.length != 0) {
            int maxSoFar = nums[0];
            int currMax = nums[0];

            for(int i = 1; i < nums.length; ++i) {
                currMax = Math.max(nums[i], currMax + nums[i]);
                maxSoFar = Math.max(maxSoFar, currMax);
            }

            return maxSoFar;
        } else {
            return 0;
        }
    }
}